package com.gxc.linkedList;

import java.util.HashMap;
import java.util.Map;

public class Copy {

    public static void main(String[] args) {
        Node head = Loopback.createNode();

        Node copyNode = mapCopy(head);

        System.out.println(compare(head, copyNode));

        copyNode = mapCopy(head);
        System.out.println(compare(head, copyNode));

        copyNode = linkCopy(head);
        System.out.println(compare(head, copyNode));
    }

    /**
     * 额外空间负责度为O(1)
     * @param head
     * @return
     */
    private static Node linkCopy(Node head) {
        Node node = head;
        Node next;
        while (node!=null) {
            next = node.next;
            Node newNode = new Node(node.value);
            node.next = newNode;
            newNode.next = next;

            node = next;
        }

        node = head;
        while (node!=null) {
            next = node.next;
            if (node.random!=null) next.random = node.random.next;

            node = next.next;
        }

        node = head;
        Node newNode = head.next;
        while (node!=null) {
            next = node.next;
            node.next = next.next;
            if (next.next!=null) next.next = node.next.next;

            node = node.next;
        }

        return newNode;
    }


    /**
     * 使用map进行链表复制
     * @param head
     * @return
     */
    private static Node mapCopy(Node head) {
        Map<Node, Node> map = new HashMap<>();

        Node node = head;
        while (node != null) {
            Node newNode = new Node(node.value);
            map.put(node, newNode);

            node = node.next;
        }

        node = head;
        while (node != null) {
            /*if (node.next!=null) map.get(node).next = map.get(node.next);
            if (node.random!=null) map.get(node).random = map.get(node.random);*/

            map.get(node).next = map.get(node.next);
            map.get(node).random = map.get(node.random);

            node = node.next;
        }
        return map.get(head);
    }

    /**
     * 比较复制的链表和原来的链表
     * @param head
     * @param copyHead
     */
    private static boolean compare(Node head, Node copyHead) {
        Node node = head;
        Node newNode = copyHead;
        while (node != null && newNode!=null) {
            if (node.value!=newNode.value) return false;
            if (node.next!=null && node.next.value!=newNode.next.value) return false;
            if (node.random!=null && node.random.value!=newNode.random.value) return false;

            node = node.next;
            newNode = newNode.next;
        }
        return true;
    }
}
